package dp;

import java.util.Arrays;

public class Solution44 {

    public static void main(String[] args) {
        String[] params = new String[]{"aab", "c*a*b"};

        System.out.println(new Solution44().isMatch(params[0], params[1]));
    }

    public boolean isMatch(String s, String p) {
        if (s == null || s.equals("") || p == null || p.equals("")) {
            if (s.equals("") && (p.equals("") || p.equals("*"))) {
                return true;
            }

            return false;
        }

        int sSize = s.length();
        boolean[] match = new boolean[sSize + 1];
        boolean[] matchTemp = new boolean[sSize + 1];
        boolean[] trueTemplate = new boolean[s.length() + 2];
        Arrays.fill(match, false);
        Arrays.fill(matchTemp, false);
        Arrays.fill(trueTemplate, true);
        match[0] = true;
        int lastMatchIndex = 0;
        for (int i = 0; i < p.length(); i++) {
            char pChar = p.charAt(i);
            int j = lastMatchIndex + pChar != '*' ? 1 : 0;
            while (j <= sSize) {
                if (pChar == '*') {
                    System.arraycopy(trueTemplate, 0, match, j, sSize - j + 1);
                    break;
                } else if (pChar == '?') {
                    match[j] = true;
                } else {
                    if (pChar == s.charAt(j - 1)) {
                        match[j] = true;
                    }
                }

                for (; j <= sSize; j++) {
                    if (matchTemp[j]) {
                        j++;
                        break;
                    }
                }
            }

            int k = 0;
            for (; k <= sSize; k++) {
                if (match[k]) {
                    break;
                }
            }
            lastMatchIndex = k;

            System.out.println("lastMatchIndex: " + lastMatchIndex + ", matchArray:" + Arrays.toString(match));
            System.arraycopy(match, 0, matchTemp, 0, sSize + 1);
            Arrays.fill(match, false);
        }

        return matchTemp[sSize];
    }

}
